package Leetcode;


/**
 * 回文链表
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 */
public class test234 {

    /**
     * 要求不空间复杂度为O（1）
     * 原链表分为来两个子链表，反转后一半链表，遍历前半和后半找是否存在不相同的对应节点值
     * 需要反转链表和寻找中间节点的辅助方法
     * @param head
     * @return
     */
    public boolean isPalindrome1(ListNode head){
        ListNode midLink=middleNode1(head);
        ListNode midLinkCounter=reverseList(midLink);
        while(midLinkCounter!=null){
            if (head.val!=midLinkCounter.val){
                return false;
            }
            head=head.next;
            midLinkCounter=midLinkCounter.next;
        }
        return true;
    }


    /**
     *使用快慢指针法
     * 快指针走两步，慢指针走一步，到快指针走到null或者快指针的下一个元素为空时，慢指针恰好在中间节点上
     * @param head
     * @return
     */
    public ListNode middleNode1(ListNode head){
        ListNode fast=head;
        ListNode low=head;
        while (fast!=null&&fast.next!=null){
            //快指针走两步
            fast=fast.next.next;
            //慢指针走一步
            low=low.next;
        }
        return low;
    }


    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode dummyHead = new ListNode();
        //遍历链表的同时建立新的链表
        while (head != null) {
            ListNode node = new ListNode(head.val);
            node.next = dummyHead.next;
            dummyHead.next = node;
            head = head.next;
        }
        return dummyHead.next;
    }

    /**
     * 空间复杂度为O（n）
     * 反转原链表，将反转后的新链表与旧链表遍历对比
     *需要反转链表的辅助方法
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode newLink = reverseList(head);
        while (head != null) {
            //同时遍历两个链表，如果有一个对应节点值不同，就返回false
            if (head.val != newLink.val) {
                return false;
            }
            head = head.next;
            newLink = newLink.next;
        }
        //此时，遍历完毕，所有对应节点值都相同，返回true
        return true;
    }





}

